package Year21_Month11.day1131;

public class HashBucket {
    //首先构造节点
    public static class ListNode{
        Integer key;
        Integer value;
        ListNode next;

        public ListNode(Integer key,Integer value){
            this.key = key;
            this.value = value;
        }
    }

    //然后对于哈希表底层结构进行设置
    ListNode[] table;
    int size;//设定有效元素个数

    public HashBucket(int cap){
        if(cap < 0){
            cap = 16;
        }
        table = new ListNode[cap];
    }

    //首先给出hash函数计算方法
    public int hashfunc(int key){
        return key % table.length;
    }

    //接着给出扩容的方法
    public void enSureCapcity(){
        int newlength = table.length * 2;
        if(size >= table.length){
            ListNode[] newtable = new ListNode[newlength];

            for(int i = 0;i < table.length;i++){
                ListNode cur = table[i];//先保存节点
                while(cur != null){
                    table[i] = cur.next;

                    int newindex = cur.key % newlength;
                    cur.next = newtable[newindex];
                    newtable[newindex] = cur;
                    cur = table[i];
                }
            }
            table = newtable;
        }
    }

    //get()方法，查找一个元素是否存在
    public Integer get(Integer key){
        int index = hashfunc(key);
        ListNode cur = table[index];
        while(cur != null){
            if(key.equals(cur.key)){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }

    //put()方法，放入一个元素
    public Integer put(Integer key,Integer value){
        int index = hashfunc(key);
        if(index > table.length){//如果情况不对，就要扩容
            enSureCapcity();
        }
        ListNode cur = table[index];

        while(cur != null){
            if(key.equals(cur.key)){
                Integer fac = cur.value;
                cur.value = value;
                return fac;
            }
        }
        ListNode newNode = new ListNode(key,value);//如果key对应的节点不存在，那么就要插入了，用头插法
        newNode.next = table[index];
        table[index] = newNode;
        size++;
        return newNode.value;
    }

    //返回key对应的value值，如果为空，就返回你设置的值
    public Integer getOrDefault(Integer key,Integer val){
        Integer fac = get(key);
        if(fac == null){
            return val;
        }
        return fac;
    }

    //删除元素
    public Integer remove(Integer key){
        int index = hashfunc(key);
        ListNode cur = table[index];
        ListNode pre = null;
        while(cur != null){
            if(key.equals(cur.key)){
                Integer oldvalue = cur.value;
                if(table[index] == cur){
                    table[index] = cur.next;
                }else{
                    pre.next = cur.next;
                }
                size--;
                cur.next = null;
                return oldvalue;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }

    //检测key存不存在
    public boolean containsKey(Integer key){
        return get(key) != null;
    }

    //检测value值存不存在
    public boolean containsValue(Integer val){
        for (int i = 0;i < table.length;i++){
            ListNode cur = table[i];
            while(cur != null){
                if(val.equals(cur.value)){
                    return true;
                }
                cur = cur.next;
            }
        }
        return false;
    }

    //检测当前有效元素个数
    public int size(){
        return size;
    }

}
